from RandomList import GetRandomList

def radix_sort(arr):
    # 支持负数的基数排序：多开10个桶存储负数的情况
    size = len(str(max(arr)))
    for i in range(size):
        buckets = [[] for _ in range(20)]
        for num in arr:
            if num <= 0:
                buckets[10 - abs(num) \
                    // (10 ** i) % 10].append(num)
            else:
                buckets[abs(num)\
                    // (10 ** i) % 10 + 10].append(num)
        arr.clear()
        for bucket in buckets:
            for num in bucket:
                arr.append(num)

    return arr

if __name__ == "__main__":
    Arr = GetRandomList(5000)
    Arr = list(map(lambda x : x - 20, Arr))
    print(radix_sort(Arr))
    